//合并 K 个升序链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct comp {
        bool operator()(ListNode* x, ListNode* y) { return x->val > y->val; }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* newhead = new ListNode(-1);
        ListNode* tail = newhead;
        priority_queue<ListNode*, vector<ListNode*>, comp> q;
        for (auto& l : lists) {
            if (l)
                q.push(l);
        }
        ListNode* temp;
        while (q.size()) {
            temp = q.top();
            tail->next = temp;
            tail = tail->next;
            q.pop();
            if (temp->next)
                q.push(temp->next);
        }
        return newhead->next;
    }
};

//K 个一组翻转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int n = 0;
        ListNode* _head = head;
        while (_head) {
            n++;
            _head = _head->next;
        }
        n /= k;
        ListNode* new_head = new ListNode(-1, head);
        ListNode* prev = new_head;
        ListNode* temp = head;
        ListNode* cur = head;
        ListNode* next = head->next;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < k; j++) {
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
                if (next)
                    next = next->next;
            }
            prev = temp;
            temp = cur;
        }
        prev->next = temp;
        return new_head->next;
    }
};